import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;

class IntCmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class PriorityQueue {

    public int[] smallestK2(int[] arr, int k){
        int[] tmp = new int[k];
        if(k == 0){
            return tmp;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue();
        for (int i = 0; i < arr.length; i++) {
            minHeap.push(arr[i]);
        }
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.pollHeap();
        }
        return tmp;
    }

    public int[] smallestK1(int[] arr, int k) {
        int[] tmp = new int[k];
        if(k == 0){
            return tmp;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new IntCmp());
        //1.把前k个元素放进堆中;
        for (int i = 0; i < k; i++) {
            minHeap.push(arr[i]);
        }
        //2.遍历剩下N - K个元素;
        for (int i = k; i < arr.length; i++) {
            int val = minHeap.peekHeap();
            if(val > arr[i]){
                minHeap.pollHeap();
                minHeap.push(arr[i]);
            }
        }
        //3.将遍历好的大堆放入数组，此时数组都是为最小元素;
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.pollHeap();
        }
        return tmp;
    }

    public int[] elem;
    public int usedSize;

    public PriorityQueue() {
        this.elem = new int[10];
    }

    public void init(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    public void createHeap() {
        for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
            shiftDown(parent,usedSize);
        }
    }

    public void swap(int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    /**
     *
     * @param parent 是每棵子树的根节点的下标
     * @param end  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int parent,int end) {
        int child = 2*parent + 1;
        while (child < end){
            if(child+1 < end && elem[child] < elem[child+1]){
                child++;
            }
            if(elem[parent] < elem[child]){
                swap(elem[parent],elem[child]);
                parent = child;
                child = 2*parent + 1;
            }else{
                break;
            }
        }
    }


    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()){
            elem = Arrays.copyOf(elem, 2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
        shiftUp(usedSize-1);
    }

    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while (parent >= 0){
            if(elem[child] > elem[parent]){
                swap(elem[child],elem[parent]);
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public int pollHeap() {
        if(isEmpty()){
            return -1;
        }
        int old = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return old;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        return elem[0];
    }
}
//判断是否有环；
//public class Solution {
//    public boolean hasCycle(ListNode head) {
//        if (head == null) {
//            return false;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        while (fast.next != null && fast.next.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if(fast == slow){
//                return true;
//            }
//        }
//        return false;
//    }
//}

//两个链表公共节点；
//public class Solution {
//    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//        //1. 假设 A 链表长
//        ListNode pl = pHead1;
//        ListNode ps = pHead2;
//        int lenA = 0;
//        int lenB = 0;
//        while (pl != null) {
//            lenA++;
//            pl = pl.next;
//        }
//
//        while (ps != null) {
//            lenB++;
//            ps = ps.next;
//        }
//        //要重新赋值
//        pl = pHead1;
//        ps = pHead2;
//
//        int len = lenA - lenB;
//        //2. 判断len是正数  还是 负数
//        if (len < 0) {
//            pl = pHead2;
//            ps = pHead1;
//            len = lenB - lenA;
//        }
//        //上述2步 走完之后
//        // pl 一定指向 最长的链表 ps 一定指向的是最短的链表
//        // len 一定是正数
//        //3. 让长链表 pl走差值len步
//        while (len != 0) {
//            pl = pl.next;
//            len--;
//        }
//        //4. 一起走 直到相遇
//        while (pl != ps) {
//            pl = pl.next;
//            ps = ps.next;
//        }
//        if (pl == null ) {
//            //如果两个引用 都为空 证明不相交
//            return null;
//        }
//        return pl;
//    }
//}
